//
// Created by ASUS on 2023/9/21.
//
/*
给你一个正整数 n ，请你返回 n 的 惩罚数 。
n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：
1 <= i <= n
i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。

示例 1：
输入：n = 10
输出：182
解释：总共有 3 个整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
因此，10 的惩罚数为 1 + 81 + 100 = 182

示例 2：
输入：n = 37
输出：1478
解释：总共有 4 个整数 i 满足要求：
- 1 ，因为 1 * 1 = 1
- 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
- 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。
- 36 ，因为 36 * 36 = 1296 ，且 1296 可以分割成 1 + 29 + 6 。
因此，37 的惩罚数为 1 + 81 + 100 + 1296 = 1478

提示：1 <= n <= 1000
 */

#include <bits/stdc++.h>
using namespace std;

int PRE_SUM[1001];

int init = []() {
	for (int i = 1; i <= 1000; i++) {
		string s = to_string(i * i);
		int n = s.length();
		function<bool(int, int)> dfs = [&](int p, int sum) -> bool {
			if (p == n)  // 递归终点
				return sum == i; // i 符合要求
			int x = 0;
			for (int j = p; j < n; j++) { // 从 s[p] 到 s[j] 组成的子串
				x = x * 10 + int(s[j] - '0'); // 对应的整数值
				if (dfs(j + 1, sum + x))
					return true;
			}
			return false;
		};
		PRE_SUM[i] = PRE_SUM[i - 1] + (dfs(0, 0) ? i * i : 0);
	}
	return 0;
}();

class Solution {
public:
	int punishmentNumber(int n) {
		return PRE_SUM[n];
	}
};
